// 步骤， 1，使用cur指针遍历一遍链表，找出链表中最大值list_max和最小值list_min
// 2. 使用数组counts存储节点出现次数
// 3. 再遍历一次链表，将链表中每个值为cur.val的节点出现次数，存入数组对应cur.val - list_min项中
// 4. 反向填充目标链表
//   1. 建立一个dummy_head,作为链表的头节点，使用cur指针指向dummy_head
//   2. 从小到大遍历一遍数组counts，对于每个counts[i] != 0的元素建立一个链接点，值为 i + list_min,将其插入到cur.next上，并向右移动cur，同时counts[i] -= 1,直到counts[i] === 0,继续向后遍历数组counts
// 将哑结点dummy_dead的下个链接点dummy_head.next作为新链表的头节点返回

// 时间复杂度：O(n + k),k代表待排序链表中所有元素的值域
// 空间复杂度：O(k)
const { LinkedList, ListNode } = require('../1. 链表基础/1. 建立线性链表')
function countingSort(head) {
    // 1. 找出链表中最大值list_max和最小值list_min
    let list_max = head.val
    let list_min = head.val
    let cur = head
    while (cur) {
        if (cur.val < list_min) {
            list_min = cur.val
        }
        if (cur.val > list_max) {
            list_max = cur.val
        }
        cur = cur.next
    }

    let size = list_max - list_min + 1
    let counts = new Array(size).fill(0)
    cur = head
    while (cur) {
        counts[cur.val - list_min] += 1
        cur = cur.next
    }

    let dummy_head = new ListNode(-1)
    cur = dummy_head
    for (let i = 0; i < size; i++) {
        while (counts[i]) {
            cur.next = new ListNode(i + list_min)
            counts[i] -= 1
            cur = cur.next
        }        
    }
    return dummy_head.next
}

const linkList = new LinkedList([2, 5, 1, 6, 3, 4])
let res = countingSort(linkList.head)
console.log(res);